package com.vinjune.algorithm.algorithms;

import java.util.Scanner;

/**
*约瑟夫问题
*已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k(1，2，3...n)的人开始报数，数到m(1，2，3...)的那个人出列；
*他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。求出圈顺序
*@author 作者：zhangwenjun
*@version 创建时间：2015年12月9日 下午5:06:30
*类说明
*/

public class Josephus {
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println("please input n k m");
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int m = sc.nextInt();
		loop(n, k, m);
	}

	public static void loop(int n, int k, int m) {
		int[] a = new int[n+1];
		a[0] = -1;
		for(int t=1;t<=n;t++)
			a[t]=t;
		k = k%n;
		int left = n; //剩下的人数
		int p = k+m-1;  //下标
		int step = m; //步长 超过m则变为1
		while(left>0) {
			if(step == m) {
				if(a[p] != -1) { //删除这个位置
					System.out.print(a[p] + " ");
					a[p] = -1;
					left--;
					step = 0;
					p++;
					if(p>n)
						p=1;
					if(a[p] != -1)
						step++;
				    }else {
					     p++;
					     if(p>n)
						     p=1;
				}
			} else {
				p++;
				if(p>n)
					p=1;
				if(a[p] != -1)
					step++;
			}
		}
	}

}


